package excercise.dynamic;

public class Luogu_P1616 {

    public int solution(int t, int[] ci, int[] vi) {
        int[][] dp = new int[ci.length + 1][t + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j <= t; j++) {
                dp[i][j] = dp[i - 1][j];
                for (int k = 1; k <= t / ci[i - 1]; k++) {
                    if (j - k * ci[i - 1] >= 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * ci[i - 1]] + vi[i - 1] * k);
                    }
                }
            }
        }
        return dp[dp.length - 1][t];
    }

    public static void main(String[] args) {
        int t = 70;
        int[] ci = {71, 69, 1};
        int[] vi = {100, 1, 2};
        int solution = new Luogu_P1616().solution(t, ci, vi);
        System.out.println("solution = " + solution);
    }
}
